class Solution {
public:
    static bool cmp(vector<int>& a,vector<int>& b){
        if(a[0] == b[0]) return a[1] > b[1];
        return a[0] < b[0];
    }
                                        
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int ret = 0;
        int n = envelopes.size();
        sort(envelopes.begin(),envelopes.end(),cmp);
        vector<int> st;
        
        for(int i = 0;i < n;i++){
            int u = envelopes[i][1];
            auto p = lower_bound(st.begin(),st.end(),u);
            if(p == st.end()){
                st.push_back(u);
                ret++;
            }else{
                *p = u;
            }
        }
        
        return ret;
    }
};
